home *** CD-ROM | disk | FTP | other *** search
/ Total Network Tools 2002 / NextStepPublishing-TotalNetworkTools2002-Win95.iso / Archive / Misc Servers / Zope.exe / KJPARSEBUILD.PY < prev    next >
Encoding:
Python Source  |  1999-11-03  |  46.5 KB  |  1,330 lines
  1. #
  2. # python code for building a parser from a grammar
  3. #  Copyright Aaron Robert Watters, 1994
  4. #
  5.  
  6. # BUGS:
  7. #  A bad grammar that has no derivations for
  8. #  the root nonterminal may cause a name error
  9. #  on the variable "GoodStartingPlace"
  10.  
  11. # this needs to be modified so the RULEGRAM is loaded from a
  12. # compiled representation if available.
  13.  
  14. import string
  15. import kjSet
  16. import kjParser
  17. import regex
  18.  
  19. # import some constants
  20. from kjParser import \
  21.  TERMFLAG, NOMATCHFLAG, MOVETOFLAG, REDUCEFLAG, TRANSFLAG, KEYFLAG, \
  22.  NONTERMFLAG, TERMFLAG, EOFFLAG, ENDOFFILETOKEN
  23.  
  24. PMODULE = kjParser.THISMODULE
  25.  
  26. # errors raised here
  27. TokenError = "TokenError" # may happen on autogen with bad grammar
  28. NotSLRError = "NotSLRError" # may happen for nonSLR grammar
  29.  
  30. # set this flag for regression testing at each load
  31. RUNTESTS = 0
  32. # set this flag to abort automatic generation on Errors
  33. ABORTONERROR = 0
  34.  
  35. # token used to mark null productions
  36. NULLTOKEN = (None,None)
  37.  
  38.  
  39. # a derived FSM class, with closure computation methods defined
  40. # (compilable FSMachine)
  41. #
  42. class CFSMachine(kjParser.FSMachine):
  43.  
  44.   def __init__(self, nonterm):
  45.       kjParser.FSMachine.__init__(self, nonterm)
  46.  
  47.   # return the epsilon closure of the FSM as a new FSM
  48.   #
  49.   # DoNullMap, if set, will map unexpected tokens to
  50.   # the "empty" state (usually creating a really big fsm)
  51.   #
  52.   def Eclosure(self, Epsilon, DoNullMaps=0):
  53.     Closure = CFSMachine( self.root_nonTerminal )
  54.     
  55.     # compute the Epsilon Graph between states
  56.     EGraph = kjSet.NewDG([])
  57.     for State in range(0,self.maxState+1):
  58.        # every state is E-connected to self
  59.        kjSet.AddArc( EGraph, State, State )
  60.        # add possible transition on epsilon (ONLY ONE SUPPORTED!)
  61.        key = (State, Epsilon)
  62.        if self.StateTokenMap.has_key(key):
  63.           keymap = self.StateTokenMap[key]
  64.           if keymap[0][0] != MOVETOFLAG:
  65.              raise TypeError, "unexpected map type in StateTokenMap"
  66.           for (Flag,ToState) in keymap:
  67.              kjSet.AddArc( EGraph, State, ToState )
  68.     #endfor
  69.     # transitively close EGraph
  70.     kjSet.TransClose( EGraph )
  71.  
  72.     # Translate EGraph into a dictionary of lists
  73.     EMap = {}
  74.     for State in range(0,self.maxState+1):
  75.        EMap[State] = kjSet.Neighbors( EGraph, State )
  76.  
  77.     # make each e-closure of each self.state a state of the closure FSM.
  78.     # here closure states assumed transient -- reset elsewhere.
  79.     # first do the initial state
  80.     Closure.States[ Closure.initial_state ] = \
  81.        [TRANSFLAG, kjSet.NewSet(EMap[self.initial_state]) ]
  82.     # do all other states (save initial and successful final states)
  83.     #for State in range(0,self.maxState+1):
  84.     #   if State != self.initial_state \
  85.     #    and State != self.successful_final_state:
  86.     #      Closure.NewSetState(TRANSFLAG, kjSet.NewSet(EMap[State]) )
  87.     ##endfor
  88.  
  89.     # compute set of all known tokens EXCEPT EPSILON
  90.     Tokens = kjSet.NewSet( [] )
  91.     for (State, Token) in self.StateTokenMap.keys():
  92.        if Token != Epsilon:
  93.           kjSet.addMember(Token, Tokens)
  94.     # tranform it into a list
  95.     Tokens = kjSet.get_elts(Tokens)
  96.  
  97.     # for each state of the the closure FSM (past final) add transitions
  98.     # and add new states as needed until all states are processed
  99.     # (uses convention that states are allocated sequentially)
  100.     ThisClosureState = 1
  101.     while ThisClosureState <= Closure.maxState:
  102.        MemberStates = kjSet.get_elts(Closure.States[ThisClosureState][1])
  103.        # for each possible Token, compute the union UTrans of all
  104.        # e-closures for all transitions for all member states,
  105.        # on the Token, make  UTrans a new state (if needed),
  106.        # and transition ThisClosureState to UTrans on Token
  107.        for Token in Tokens:
  108.           UTrans = kjSet.NewSet( [] )
  109.           for MState in MemberStates:
  110.               # if MState has a transition on Token, include 
  111.               # EMap for the destination state
  112.               key = (MState, Token)
  113.               if self.StateTokenMap.has_key(key):
  114.                  DStateTup = self.StateTokenMap[key]
  115.                  if DStateTup[0][0] != MOVETOFLAG:
  116.                     raise TypeError, "unknown map type"
  117.                  for (DFlag, DState) in DStateTup:
  118.                     for EDState in EMap[DState]:
  119.                        kjSet.addMember(EDState, UTrans)
  120.               #endif
  121.           #endfor MState
  122.           # register UTrans as a new state if needed
  123.           UTState = Closure.NewSetState(TRANSFLAG, UTrans)
  124.           # record transition from
  125.           # ThisClosureState to UTState on Token
  126.           if DoNullMaps:
  127.              Closure.SetMap( ThisClosureState, Token, UTState)
  128.           else:
  129.              if not kjSet.Empty(UTrans):
  130.                 Closure.SetMap( ThisClosureState, Token, UTState)
  131.        #endfor Token
  132.        ThisClosureState = ThisClosureState +1
  133.     #endwhile
  134.     return Closure
  135.   #enddef Eclosure
  136.  
  137.   # add an set-marked state to self if not present
  138.   # uses self.States[s][1] as the set marking the state s
  139.   #
  140.   # only used by Eclosure above
  141.   #
  142.   def NewSetState(self, kind, InSet):
  143.     # return existing state if one is present that matches the set
  144.     LastState= self.maxState
  145.     # skip state 0 (successful final state)???
  146.     for State in range(1,LastState+1):
  147.        MarkSet = self.States[State][1]
  148.        if kjSet.Same(InSet,MarkSet):
  149.           return State  # nonlocal
  150.     #endfor
  151.     # if not exited then allocate a new state
  152.     LastState = LastState + 1
  153.     self.States[LastState] = [ kind , InSet ]
  154.     self.maxState = LastState
  155.     return LastState
  156.   #enddef newSetState
  157.  
  158. #endclass CFSMachine
  159.  
  160.  
  161. # Ruleset class, used to compute NFA and then DFA for
  162. #  parsing based on a list of rules.
  163. #
  164. class ruleset:
  165.  
  166.   def __init__(self, StartNonterm, Rulelist):
  167.     # initialize the ruleset
  168.     self.StartNonterm = StartNonterm
  169.     self.Rules = Rulelist
  170.  
  171.   # method to compute prefixes and First sets for nonterminals
  172.   def CompFirst(self):
  173.      # uses the special null production token NULLTOKEN
  174.      # snarfed directly from Aho+Ullman (terminals glossed)
  175.      First = kjSet.NewDG( [] )
  176.      # repeat the while loop until no change is made to First
  177.      done = 0
  178.      while not done:
  179.        done = 1 # assume we're done until a change is made to First
  180.  
  181.        # iterate through all rules looking for a new arc to add
  182.        # indicating Terminal > possible first token derivation
  183.        #
  184.        for R in self.Rules:
  185.            GoalNonterm = R.Nonterm
  186.            Bodylength = len(R.Body)
  187.            # look through the body of the rule up to the token with
  188.            # no epsilon production (yet seen)
  189.            Bodyindex = 0
  190.            Processindex = 1
  191.            while Processindex:
  192.               # unless otherwise indicated below, don't go to next token
  193.               Processindex = 0
  194.  
  195.               # if index is past end of body then record
  196.               # an epsilon production for this nonterminal
  197.               if Bodyindex >= Bodylength:
  198.                  if not kjSet.HasArc(First, GoalNonterm, NULLTOKEN ):
  199.                     kjSet.AddArc( First, GoalNonterm, NULLTOKEN )
  200.                     done = 0 # change made to First
  201.               else:
  202.                  # otherwise try to add firsts of this token
  203.                  # to firsts of the Head of the rule.
  204.                  Token = R.Body[Bodyindex]
  205.                  (type, name) = Token
  206.                  if type in (KEYFLAG,TERMFLAG):
  207.                     # try to add this terminal to First for GoalNonterm
  208.                     if not kjSet.HasArc(First, GoalNonterm, Token):
  209.                        kjSet.AddArc( First, GoalNonterm, Token)
  210.                        done = 0
  211.                  elif type == NONTERMFLAG:
  212.                     # try to add each First entry for nonterminal
  213.                     # to First entry for GoalNonterm
  214.                     for FToken in kjSet.Neighbors( First, Token ):
  215.                        if not kjSet.HasArc(First, GoalNonterm, FToken):
  216.                           kjSet.AddArc( First, GoalNonterm, FToken)
  217.                           done = 0
  218.                     # does this nonterminal have a known e production?
  219.                     if kjSet.HasArc( First, Token, NULLTOKEN ):
  220.                        # if so, process next token in rule
  221.                        Processindex = 1
  222.                  else:
  223.                     raise TokenError, "unknown token type in rule body"
  224.               #endif
  225.               Bodyindex = Bodyindex + 1
  226.            #endwhile Processindex
  227.        #endfor R in self.Rules
  228.      #endwhile not done
  229.      self.First = First
  230.   #enddef CompFirst 
  231.  
  232.   # computing the Follow set for the ruleset
  233.   # the good news: I think it's correct.
  234.   # the bad news: It's slower than it needs to be for epsilon cases.
  235.   def CompFollow(self):
  236.      Follow = kjSet.NewDG( [] )
  237.  
  238.      # put end marker on follow of start nonterminal
  239.      kjSet.AddArc(Follow, self.StartNonterm, kjParser.ENDOFFILETOKEN)
  240.  
  241.      # now compute other follows using the rules;
  242.      # repeat the loop until no change to Follow.
  243.      done = 0
  244.      while not done:
  245.        done = 1 # assume done unless Follow changes
  246.        for R in self.Rules:
  247.           #print R
  248.           # work backwards in the rule body to
  249.           # avoid retesting for epsilon nonterminals
  250.           Bodylength = len(R.Body)
  251.           EpsilonTail = 1 # the tail of rule may expand to null
  252.           BodyIndex = Bodylength - 1
  253.           Last = 1 # loop starts at the last
  254.           from types import TupleType
  255.           while BodyIndex >= 0:
  256.              Token = R.Body[BodyIndex]
  257.              (Ttype,Tname) = Token
  258.              if Ttype in (KEYFLAG,TERMFLAG):
  259.                 # keywords etc cancel epsilon tail, otherwise ignore
  260.                 EpsilonTail = 0
  261.              elif Ttype == NONTERMFLAG:
  262.                 # if the tail expands to epsilon, map
  263.                 # follow for the goal nonterminal to this token
  264.                 # and also follow for the tail nonterms
  265.                 if EpsilonTail:
  266.                    # add follow for goal
  267.                    for FToken in kjSet.Neighbors(Follow,R.Nonterm):
  268.                       if not kjSet.HasArc(Follow,Token,FToken):
  269.                          kjSet.AddArc(Follow,Token,FToken)
  270.                          #if type(FToken[0])==TupleType:
  271.                          #   raise ValueError, "bad FToken"+`FToken`
  272.                          #print "new", Token, FToken
  273.                          done = 0 # follow changed, loop again
  274.                    # add follow for tail members
  275.                    #for Index2 in range(BodyIndex+1, Bodylength):
  276.                    #   TailToken = R.Body[Index2]
  277.                    #   for FToken in kjSet.Neighbors(Follow,TailToken):
  278.                    #       if not kjSet.HasArc(Follow,Token,FToken):
  279.                    #          kjSet.AddArc(Follow,Token,FToken)
  280.                    #          done = 0
  281.                 #endif EpsilonTail
  282.  
  283.                 # if we are not at the end use First set for next token
  284.                 if not Last:
  285.                    NextToken = R.Body[BodyIndex+1]
  286.                    (NTtype, NTname) = NextToken
  287.                    if NTtype in (KEYFLAG,TERMFLAG):
  288.                       if not kjSet.HasArc(Follow,Token,NextToken):
  289.                          kjSet.AddArc(Follow,Token,NextToken)
  290.                          #print "next", Token, NextToken
  291.                          done = 0
  292.                    elif NTtype == NONTERMFLAG:
  293.                       for FToken in kjSet.Neighbors(self.First, NextToken):
  294.                          if FToken != NULLTOKEN:
  295.                             if not kjSet.HasArc(Follow,Token,FToken):
  296.                                kjSet.AddArc(Follow,Token,FToken)
  297.                                #print "neighbor", Token, FToken
  298.                                done = 0
  299.                          else:
  300.                             # next token expands to epsilon:
  301.                             # add its follow, unless already done above
  302.                             #if not EpsilonTail:
  303.                             for FToken in kjSet.Neighbors(Follow,NextToken):
  304.                                 if not kjSet.HasArc(Follow,Token,FToken):
  305.                                    kjSet.AddArc(Follow,Token,FToken)
  306.                                    #print "epsilon", Token, FToken
  307.                                    done = 0
  308.                    else:
  309.                      raise TokenError, "unknown token type in rule body"
  310.                 #endif not Last
  311.  
  312.                 # finally, check whether next iteration has epsilon tail
  313.                 if not kjSet.HasArc(self.First, Token, NULLTOKEN):
  314.                    EpsilonTail = 0
  315.              else:
  316.                 raise TokenError, "unknown token type in rule body"
  317.  
  318.              BodyIndex = BodyIndex - 1
  319.              Last = 0 # no longer at the last token of the rule
  320.           #endwhile
  321.        #endfor
  322.      #endwhile
  323.      self.Follow = Follow
  324.   #enddef CompFollow
  325.  
  326.   def DumpFirstFollow(self):
  327.      First = self.First
  328.      Follow = self.Follow
  329.      print "First:"
  330.      for key in First.keys():
  331.          name = key[1]
  332.          print name," :: ",
  333.          for (flag2,name2) in First[key].keys():
  334.              print name2,", ",
  335.          print
  336.      print "Follow:"
  337.      for key in Follow.keys():
  338.          name = key[1]
  339.          print name," :: ",
  340.          for (flag2,name2) in Follow[key].keys():
  341.              print name2,", ",
  342.          print
  343.  
  344.   # computing the "first" of the tail of a rule followed by an
  345.   #  optional terminal
  346.   # doesn't include NULLTOKEN
  347.   # requires self.First to be computed
  348.   #
  349.   def FirstOfTail(self, Rule, TailIndex, Token=None):
  350.      Result = kjSet.NewSet( [] )
  351.      # go through all tokens in rule tail so long as there is a
  352.      #  null derivation for the remainder
  353.      Nullprefix = 1
  354.      BodyLength = len(Rule.Body)
  355.      ThisIndex = TailIndex
  356.      while Nullprefix and ThisIndex < BodyLength:
  357.         RToken = Rule.Body[ThisIndex]
  358.         (RTtype, RTname) = RToken
  359.         if RTtype == NONTERMFLAG:
  360.            for FToken in kjSet.Neighbors(self.First, RToken):
  361.                if FToken != NULLTOKEN:
  362.                   kjSet.addMember(FToken, Result)
  363.            #endfor
  364.            # check whether this symbol might have a null production
  365.            if not kjSet.HasArc(self.First, RToken, NULLTOKEN):
  366.               Nullprefix = 0
  367.         elif RTtype in [KEYFLAG, TERMFLAG]:
  368.            kjSet.addMember(RToken, Result)
  369.            Nullprefix = 0
  370.         else:
  371.            raise TokenError, "unknown token type in rule body"
  372.         ThisIndex = ThisIndex + 1
  373.      #endwhile
  374.      # add the optional token if given and Nullprefix still set
  375.      if Nullprefix and Token != None:
  376.         kjSet.addMember(Token, Result)
  377.      return Result
  378.   #enddef FirstOfTail
  379.  
  380.   # compute an SLR NFA for the ruleset with states for each SLR "item"
  381.   # and transitions, eg:
  382.   #     X > .AB
  383.   #   on A maps to X > A.B
  384.   #   on epsilon maps to A > .ZC
  385.   #                  and A > .WK
  386.   # an item is a pair (rulenumber, bodyposition)
  387.   # where body position 0 is interpreted to point before the
  388.   # beginning of the body.
  389.   #
  390.   # SLR = "simple LR" in Aho+Ullman terminology
  391.   #
  392.   def CompSLRNFA(self):
  393.      NFA = CFSMachine(self.StartNonterm)
  394.      Nrules = len(self.Rules)
  395.      itemStateMap = {}
  396.      for Ruleindex in range(0,Nrules):
  397.         Rule = self.Rules[Ruleindex]
  398.         # make an item for each "dot" position in the body
  399.         for DotPos in range(0, len(Rule.Body) + 1):
  400.            item = (Ruleindex, DotPos)
  401.            itemState = NFA.NewState(TRANSFLAG, [item])
  402.            itemStateMap[item] = itemState
  403.         #endfor DotPos
  404.      #endfor Ruleindex
  405.  
  406.      # now that the states are initialized
  407.      # compute transitions except for the last item of a rule
  408.      # (which has none)
  409.      for Ruleindex in range(0,Nrules):
  410.         Rule = self.Rules[Ruleindex]
  411.         for DotPos in range(0, len(Rule.Body)):
  412.            item = (Ruleindex, DotPos)
  413.            CurrentToken = Rule.Body[DotPos]
  414.            ThisState = itemStateMap[item]
  415.            NextState = itemStateMap[ (Ruleindex, DotPos + 1) ]
  416.            NFA.SetMap( ThisState, CurrentToken, NextState  )
  417.            # if the current token is a nonterminal
  418.            # ad epsilon transitions to first item for any
  419.            # rule that derives this nonterminal
  420.            (CTtype, CTname) = CurrentToken
  421.            if CTtype == NONTERMFLAG:
  422.               for Rule2index in range(0,Nrules):
  423.                  Rule2 = self.Rules[Rule2index]
  424.                  Head = Rule2.Nonterm
  425.                  if Head == CurrentToken:
  426.                     NextState = itemStateMap[( Rule2index, 0 )]
  427.                     NFA.SetMap( ThisState, NULLTOKEN, NextState )
  428.               #endfor Rule2index
  429.            #endif CTtype == NONTERMFLAG
  430.         #endfor DotPos
  431.      #endfor Ruleindex
  432.  
  433.      # must handle the initial state properly here!
  434.      # Make a dummy state with e-transitions to all first items
  435.      # for rules that derive the initial nonterminal
  436.      ThisState = NFA.initial_state
  437.      GoodStartingPlace = None
  438.      for Ruleindex in range(0,Nrules):
  439.         Rule = self.Rules[Ruleindex]
  440.         Head = Rule.Nonterm
  441.         if Head == self.StartNonterm:
  442.            GoodStartingPlace= (Ruleindex, 0)
  443.            NextState = itemStateMap[ GoodStartingPlace ]
  444.            NFA.SetMap( ThisState, NULLTOKEN, NextState )
  445.      # fix the NFA.States entry
  446.      if GoodStartingPlace == None:
  447.         raise NotSLRError, "No derivation for root nonterminal."
  448.      NFA.States[ NFA.initial_state ] = \
  449.           [ 'transient', GoodStartingPlace ]
  450.  
  451.      self.SLRNFA = NFA
  452.   #enddef CompSLRNFA
  453.  
  454.   # dump an item
  455.   def ItemDump(self, item):
  456.      (ruleindex, position) = item
  457.      Rule = self.Rules[ruleindex]
  458.      print Rule.Nonterm[1],' >> ',
  459.      for bindex in range(0, len(Rule.Body)):
  460.         if position == bindex:
  461.            print " (*) ",
  462.         print Rule.Body[bindex][1],
  463.      if position == len(Rule.Body):
  464.         print " (*) "
  465.      else:
  466.         print
  467.  
  468.   # utility function -- returns true if an item is a final item
  469.   def SLRItemIsFinal(self, item):
  470.      (ruleindex, position) = item
  471.      Rule = self.Rules[ruleindex]
  472.      if position == len(Rule.Body):
  473.         return 1
  474.      else:
  475.         return 0
  476.  
  477.   # dump the NFA
  478.   def DumpSLRNFA(self):
  479.      NFA = self.SLRNFA
  480.      print "root: ", NFA.root_nonTerminal
  481.      for key in NFA.StateTokenMap.keys():
  482.         map = NFA.StateTokenMap[key]
  483.         (fromstate, token) = key
  484.         fromitem = NFA.States[ fromstate ][1]
  485.         self.ItemDump(fromitem)
  486.         print " on ", token[1], " maps "
  487.         for Tostate in map:
  488.            Toitem = NFA.States[Tostate][1]
  489.            print "    ",
  490.            self.ItemDump(Toitem)
  491.  
  492.   # compute DFA for ruleset by computing the E-closure of the
  493.   # NFA
  494.   def CompDFA(self):
  495.      self.DFA = self.SLRNFA.Eclosure(NULLTOKEN)
  496.  
  497.   def DumpDFAsets(self):
  498.      DFA = self.DFA
  499.      print "root: ", DFA.root_nonTerminal
  500.      for State in range(1, len(DFA.States) ):
  501.         self.DumpItemSet(State)
  502.  
  503.   def DumpItemSet(self,State):
  504.      DFA = self.DFA
  505.      NFA = self.SLRNFA
  506.      print
  507.      print "STATE ", State, " *******"
  508.      fromNFAindices = kjSet.get_elts(DFA.States[State][1])
  509.      for NFAindex in fromNFAindices:
  510.         item = NFA.States[NFAindex][1]
  511.         print "  ", NFAindex, ": ",
  512.         self.ItemDump(item)
  513.  
  514.   # this function completes the computation of an SLR DFA
  515.   # by adding reduction states for each DFA state S containing
  516.   # item   H > B.
  517.   # which reduces rule H > B
  518.   # for each token T in Follow of H.
  519.   # if S already has a transition for T then there is a conflict!
  520.   #
  521.   # assumes DFA and SLRNFA and Follow have been computed.
  522.   #
  523.   def SLRFixDFA(self):
  524.      DFA = self.DFA
  525.      NFA = self.SLRNFA
  526.      # look through the states (except 0=success) of the DFA
  527.      # initially don't add any new states, just record
  528.      # actions to be done
  529.      #   uses convention that 0 is successful final state
  530.  
  531.      # ToDo is a dictionary which maps 
  532.      #     (State, Token) to a item to reduce
  533.      ToDo = {}
  534.      Error = None
  535.      for State in range(1, len(DFA.States) ):
  536.         # look for a final item for a rule in this state
  537.         fromNFAindices = kjSet.get_elts(DFA.States[State][1])
  538.         for NFAindex in fromNFAindices:
  539.            item = NFA.States[NFAindex][1]
  540.            # if the item is final remember to do the reductions...
  541.            if self.SLRItemIsFinal(item):
  542.               (ruleindex, position) = item
  543.               Rule = self.Rules[ruleindex]
  544.               Head = Rule.Nonterm
  545.               Following = kjSet.Neighbors( self.Follow, Head )
  546.               for Token in Following:
  547.                  key = (State, Token)
  548.                  if not ToDo.has_key(key):
  549.                     ToDo[ key ] = item
  550.                  else:
  551.                     # it might be okay if the items are identical?
  552.                     item2 = ToDo[key]
  553.                     if item != item2:
  554.                        print "reduce/reduce conflict on ",key
  555.                        self.ItemDump(item)
  556.                        self.ItemDump(item2)
  557.                     Error = " apparent reduce/reduce conflict"
  558.                  #endif
  559.               #endfor
  560.            #endif
  561.         #endfor NFAindex
  562.      #endfor State
  563.  
  564.      # for each (State,Token) pair which indicates a reduction
  565.      # record the reduction UNLESS the map is already set for the pair
  566.      for key in ToDo.keys():
  567.         (State,Token) = key
  568.         item = ToDo[key]
  569.         (rulenum, dotpos) = item
  570.         ExistingMap = DFA.map( State, Token )
  571.         if ExistingMap[0] == NOMATCHFLAG:
  572.            DFA.SetReduction( State, Token, rulenum )
  573.         else:
  574.            print "apparent shift/reduce conflict"
  575.            print "reduction: ", key, ": "
  576.            self.ItemDump(item)
  577.            print "existing map ", ExistingMap
  578.            Error = " apparent shift/reduce conflict"
  579.      #endfor
  580.      if Error and ABORTONERROR:
  581.         raise NotSLRError, Error
  582.   #enddef SLRfixDFA()
  583.  
  584.   # do complete SLR DFA creation starting after initialization
  585.   def DoSLRGeneration(self):
  586.      self.CompFirst()
  587.      self.CompFollow()
  588.      self.CompSLRNFA()
  589.      self.CompDFA()
  590.      self.SLRFixDFA()
  591.  
  592. #endclass ruleset
  593.  
  594.  
  595. ################ the following are interpretation functions
  596. ################ used by RULEGRAM meta grammar
  597. # some constants used here
  598. COMMENTFORM = "##.*\n"
  599. RSKEY = "@R"
  600. COLKEY = "::"
  601. LTKEY = ">>"
  602. IDNAME = "ident"
  603. # an identifier in the meta grammar is any nonwhite string
  604. # except the keywords @R :: >> or comment flag ##
  605. IDFORM = "[^" + string.whitespace + "]+"
  606.  
  607. # for identifiers simply return the string
  608. def IdentFun(string):
  609.   return string
  610.  
  611. # RootReduction should receive list of form
  612. #   [ nontermtoken, keyword COLKEY, RuleList ]
  613. def RootReduction(list, ObjectGram):
  614.   if len(list) != 3 or list[1] != COLKEY:
  615.      raise FlowError, "unexpected metagrammar root reduction"
  616.   return (list[0], list[2])
  617.  
  618. # NullRuleList should receive list of form
  619. #   []
  620. def NullRuleList(list, ObjectGram):
  621.   if list != []:
  622.      raise FlowError, "unexpected null RuleList form"
  623.   return []
  624.  
  625. # FullRuleList should receive list of form
  626. #   [ Rule, RuleList ]
  627. def FullRuleList(list, ObjectGram):
  628.   if type(list) != type([]) or len(list)!=2:
  629.      raise FlowError, "unexpected full RuleList form"
  630.   NewRule = list[0]
  631.   OldRules = list[1]
  632.   return [NewRule] + OldRules
  633.  
  634. # InterpRule should receive list of form
  635. #   [keyword RSKEY, 
  636. #    RuleNameStr, 
  637. #    keyword COLKEY, 
  638. #    Nontermtoken, 
  639. #    keyword LTKEY, 
  640. #    Bodylist]
  641. #
  642. def InterpRule(list, ObjectGram):
  643.   # check keywords:
  644.   if len(list) != 6 or \
  645.      list[0] != RSKEY or \
  646.      list[2] != COLKEY or \
  647.      list[4] != LTKEY:
  648.      raise FlowError, "unexpected meta rule reduction form"
  649.   ruleName = list[1]
  650.   ruleNonterm = list[3]
  651.   ruleBody = list[5]
  652.   # upcase the the representation of keywords if needed
  653.   if not ObjectGram.LexD.isCaseSensitive():
  654.      for i in range(0,len(ruleBody)):
  655.         (flag, name) = ruleBody[i]
  656.         if flag == KEYFLAG:
  657.            ruleBody[i] = (KEYFLAG, string.upper(name))
  658.         elif not flag in (TERMFLAG, NONTERMFLAG):
  659.            raise FlowError, "unexpected rule body member"
  660.   rule = kjParser.ParseRule( ruleNonterm, ruleBody )
  661.   rule.Name = ruleName
  662.   return rule
  663.  
  664. # InterpRuleName should receive
  665. #    [ string ]
  666. def InterpRuleName(list, ObjectGram):
  667.   #print list
  668.   # add error checking?
  669.   return list[0]
  670.  
  671. # InterpNonTerm should receive
  672. #    [ string ]  
  673. def InterpNonTerm(list, ObjectGram):
  674.   #print list
  675.   if type(list)!=type([]) or len(list)!=1:
  676.      raise FlowError, "unexpected rulename form"
  677.   Name = list[0]
  678.   # determine whether this is a valid nonterminal
  679.   if not ObjectGram.NonTermDict.has_key(Name):
  680.      #print Name
  681.      raise TokenError, "LHS of Rule must be nonterminal: "+Name
  682.   return ObjectGram.NonTermDict[Name]
  683.  
  684. # NullBody should receive []
  685. def NullBody(list, ObjectGram):
  686.   #print list
  687.   if list != []:
  688.      raise FlowError, "unexpected null Body form"
  689.   return []
  690.  
  691. # FullBody should receive
  692. #  [ string, Bodylist]
  693. # must determine whether the string represents
  694. # a keyword, a nonterminal, or a terminal of the object
  695. # grammar.
  696. # returns (KEYFLAG, string) (TERMFLAG, string) or
  697. #         (NONTERMFLAG, string) respectively
  698. #
  699. def FullBody(list,ObjectGram):
  700.   #print list
  701.   if type(list)!=type([]) or len(list)!=2:
  702.      raise FlowError, "unexpected body form"
  703.   Name = list[0]
  704.   # Does the Name rep a nonterm, keyword or term
  705.   # of the object grammar (in that order).
  706.   if ObjectGram.NonTermDict.has_key(Name):
  707.      kind = NONTERMFLAG
  708.   elif ObjectGram.LexD.keywordmap.has_key(Name):
  709.      kind = KEYFLAG
  710.   elif ObjectGram.TermDict.has_key(Name):
  711.      kind = TERMFLAG
  712.   else:
  713.      raise TokenError, "Rule body contains unregistered string: "+Name
  714.   restOfBody = list[1]
  715.   return [(kind, Name)] + restOfBody
  716.  
  717. # function to generate a grammar for parsing grammar rules
  718. #
  719. def ruleGrammar():
  720.    LexD = kjParser.LexDictionary()
  721.    # use SQL/Ansi style comments
  722.    LexD.comment( COMMENTFORM )
  723.    # declare keywords
  724.    RStart = LexD.keyword( RSKEY )
  725.    TwoColons = LexD.keyword( COLKEY )
  726.    LeadsTo = LexD.keyword( LTKEY )
  727.    # declare terminals
  728.    ident = LexD.terminal(IDNAME, IDFORM, IdentFun )
  729.    # declare nonterminals
  730.    Root = kjParser.nonterminal("Root")
  731.    Rulelist = kjParser.nonterminal("RuleList")
  732.    Rule = kjParser.nonterminal("Rule")
  733.    RuleName = kjParser.nonterminal("RuleName")
  734.    NonTerm = kjParser.nonterminal("NonTerm")
  735.    Body = kjParser.nonterminal("Body")
  736.  
  737.    # declare rules
  738.    #   Root >> NonTerm :: Rulelist
  739.    InitRule = kjParser.ParseRule( Root, \
  740.                [NonTerm, TwoColons, Rulelist], RootReduction )
  741.    #   Rulelist >>
  742.    RLNull = kjParser.ParseRule( Rulelist, [], NullRuleList)
  743.    #   Rulelist >> Rule Rulelist
  744.    RLFull = kjParser.ParseRule( Rulelist, [Rule,Rulelist], FullRuleList)
  745.    #   Rule >> "@R :: NonTerm >> Body
  746.    RuleR = kjParser.ParseRule( Rule, \
  747.       [RStart, RuleName, TwoColons, NonTerm, LeadsTo, Body],\
  748.       InterpRule)
  749.    #   Rulename >> ident
  750.    RuleNameR = kjParser.ParseRule( RuleName, [ident], InterpRuleName)
  751.    #   NonTerm >> ident
  752.    NonTermR = kjParser.ParseRule( NonTerm, [ident], InterpNonTerm)
  753.    #   Body >>
  754.    BodyNull = kjParser.ParseRule( Body, [], NullBody)
  755.    #   Body >> ident Body
  756.    BodyFull = kjParser.ParseRule( Body, [ident,Body], FullBody)
  757.  
  758.    # declare Rules list and Associated Name dictionary
  759.    Rules = [RLNull, RLFull, RuleR, RuleNameR, NonTermR,\
  760.                 BodyNull, BodyFull, InitRule]
  761.    RuleDict = \
  762.     { "RLNull":0, "RLFull":1, "RuleR":2, "RuleNameR":3, \
  763.       "NonTermR":4, "BodyNull":5, "BodyFull":6 , "InitRule":7 }
  764.    # make the RuleSet and compute the associate DFA
  765.    RuleSet = ruleset( Root, Rules )
  766.    RuleSet.DoSLRGeneration()
  767.    # construct the Grammar object
  768.    Result = kjParser.Grammar( LexD, RuleSet.DFA, Rules, RuleDict )
  769.    return Result
  770.    
  771. #enddef RuleGrammar()
  772.  
  773.  
  774. # this is the rule grammar object for 
  775. # parsing
  776. RULEGRAM = ruleGrammar()
  777.  
  778. # a derived grammar class (object oriented programming is cool!)
  779. # this is a compilable grammar for automatic parser generation.
  780. #
  781. class CGrammar(kjParser.Grammar):
  782.  
  783.    # initialization is handled by the base class
  784.  
  785.    # insert a white separated list of keywords into the LexD
  786.    # THIS SHOULD CHECK FOR KEYWORD/NONTERMINAL/PUNCT NAME
  787.    # COLLISIONS (BUT DOESN'T YET).
  788.    def Keywords(self, Stringofkeys):
  789.      keywordlist = string.split(Stringofkeys)
  790.      for keyword in keywordlist:
  791.         self.LexD.keyword( keyword )
  792.  
  793.    # insert a string of punctuations into the LexD
  794.    def punct(self, Stringofpuncts):
  795.      for p in Stringofpuncts:
  796.         self.LexD.punctuation(p)
  797.  
  798.    # register a list of regular expression strings
  799.    # to represent comments in LexD
  800.    def comments(self, listOfCommentStrings):
  801.      for str in listOfCommentStrings:
  802.         self.LexD.comment(str)
  803.  
  804.    # register a white separated list of nonterminal strings
  805.    def Nonterms(self, StringofNonterms):
  806.      nonTermlist = string.split(StringofNonterms)
  807.      for NonTerm in nonTermlist:
  808.         self.NonTermDict[NonTerm] = kjParser.nonterminal(NonTerm)
  809.  
  810.    # initialize or add more rules to the RuleString
  811.    def Declarerules(self, StringWithRules):
  812.      self.RuleString = self.RuleString + "\n" + StringWithRules
  813.  
  814.    # The compilation function assumes
  815.    #   NonTermDict
  816.    #   RuleString
  817.    #   LexD
  818.    #   TermDict
  819.    # have all been set up properly
  820.    # (at least if the default MetaGrammar is used).
  821.    # On successful completion it will set up
  822.    #   DFA
  823.    #   RuleL
  824.    #   RuleNameToIndex
  825.    def Compile(self, MetaGrammar=RULEGRAM):
  826.      # the following should return a list of rules
  827.      # with punctuations of self.LexD interpreted as trivial keywords
  828.      #   keywords of seld.LexD interpreted as keywords
  829.      # and nonterminals registered in NonTermDict interpreted as
  830.      # nonterms.
  831.      #  ParseResult should be of form ( (rootNT, RuleL), self )
  832.      ParseResult = MetaGrammar.DoParse1( self.RuleString, self )
  833.      (RootNonterm, Rulelist) = ParseResult
  834.  
  835.      # make a ruleset and compute its DFA
  836.      RuleS = ruleset( RootNonterm, Rulelist )
  837.      RuleS.DoSLRGeneration() 
  838.  
  839.      # make the rulename to index map to allow future bindings
  840.      for i in range(0,len(Rulelist)):
  841.         Rule = Rulelist[i]
  842.         self.RuleNameToIndex[ Rule.Name ] = i
  843.  
  844.      # fill in the blanks
  845.      self.DFA = RuleS.DFA
  846.      self.RuleL = Rulelist
  847.  
  848.      # FOR DEBUG AND TESTING
  849.      self.Ruleset = RuleS
  850.      
  851.      # DON'T clean up the grammar (misc structures are used)
  852.      # in future bindings
  853.    #enddef Compile
  854.  
  855.  
  856.    # Write a reconstructable representation for this grammar
  857.    # to a file
  858.    #EXCEPT: 
  859.    #   - rule associations to reduction functions
  860.    #     will be lost (must be reset elsewhere)
  861.    #   - terminals in the lexical dictionary
  862.    #     will not be initialized
  863.    #
  864.    # IND is used for indentation, should be whitespace (add check!)
  865.    #
  866.    # FName if given will cause the reconstructed to be placed
  867.    # inside a function `FName`+"()" returning the grammar object
  868.    #
  869.    # NOTE: this function violates information hiding principles;
  870.    #  in particular it "knows" the guts of the FSM and LexD classes
  871.    #
  872.    def Reconstruct(self, VarName, Tofile, FName=None, indent=""):
  873.       Reconstruction = codeReconstruct(VarName, Tofile, self, FName, indent)
  874.       GrammarDumpSequence(Reconstruction)
  875.    #enddef Reconstruct
  876.  
  877.    # marshalling of a grammar to a file
  878.    def MarshalDump(self, Tofile):
  879.       Reconstruction = marshalReconstruct(self, Tofile)
  880.       GrammarDumpSequence(Reconstruction)
  881.  
  882. #endclass CGrammar
  883.  
  884. # general procedure for different types of archiving for grammars
  885. def GrammarDumpSequence(ReconstructObj):
  886.    # assume an initialized Reconstruct Object with appropriate grammar etc.
  887.    # put the lexical part
  888.    ReconstructObj.PutLex()
  889.    # put the rules
  890.    ReconstructObj.PutRules()
  891.    # put transitions
  892.    ReconstructObj.PutTransitions()
  893.    # finish up
  894.    ReconstructObj.Cleanup()
  895.  
  896. # function to create a "null CGrammar"
  897. def NullCGrammar():
  898.    return CGrammar(None,None,None,{})
  899.  
  900. # utility classes -- Grammar reconstruction objects
  901. #  encapsulate the process of grammar archiving.
  902. #
  903. class Reconstruct:
  904.  
  905.    # this "virtual class" is only for common behaviors of subclasses.
  906.    def MakeTokenArchives(self):
  907.      # make a list of all tokens and
  908.      # initialize token > int dictionary
  909.      keys = self.Gram.DFA.StateTokenMap.keys()
  910.      tokenToInt = {}
  911.      tokenSet = kjSet.NewSet([])
  912.      for k in keys:
  913.          kjSet.addMember(k[1], tokenSet)
  914.      tokens = kjSet.get_elts(tokenSet)
  915.      for i in range(0,len(tokens)):
  916.          tokenToInt[ tokens[i] ] = i
  917.  
  918.      self.keys = keys
  919.      self.tokens = tokens # global sub
  920.      self.tokInt = tokenToInt # global sub
  921.  
  922. # grammar reconstruction to a file
  923. class codeReconstruct(Reconstruct):
  924.  
  925.    def __init__(self, VarName, Tofile, Grammar, FName=None, indent =""):
  926.      # do global subs for each of these
  927.      self.Var = VarName
  928.      self.File = Tofile
  929.      self.FName = FName
  930.      self.Gram = Grammar
  931.      
  932.      # put the reconstruction in a function if FName is given
  933.      if FName != None:
  934.         Tofile.write("\n\n")
  935.         Tofile.write(indent+"def "+FName+"():\n")
  936.         IND = indent+"   "
  937.      else:
  938.         IND = indent
  939.      self.I = IND # global sub!
  940.      Tofile.write("\n\n")
  941.      Tofile.write(IND+"# ******************************BEGIN RECONSTRUCTION\n")
  942.      Tofile.write(IND+"# Python declaration of Grammar variable "+VarName+".\n")
  943.      Tofile.write(IND+"# automatically generated by module "+PMODULE+".\n")
  944.      Tofile.write(IND+"# Altering this sequence by hand will probably\n")
  945.      Tofile.write(IND+"# leave it unusable.\n")
  946.      Tofile.write(IND+"#\n")
  947.      Tofile.write(IND+"import "+PMODULE+"\n\n")
  948.      Tofile.write(IND+"# variable declaration:\n")
  949.      Tofile.write(IND+VarName+"= "+PMODULE+".NullGrammar()\n\n")
  950.  
  951.      # make self.keys list of dfa keys,
  952.      #      self.tokens list of grammar tokens,
  953.      #      self.tokInt inverted dictionary for self.tokens
  954.      self.MakeTokenArchives()
  955.  
  956.      Tofile.write("\n\n"+IND+"# case sensitivity behavior for keywords.\n")
  957.      if self.Gram.LexD.isCaseSensitive():
  958.         Tofile.write(IND+VarName+".SetCaseSensitivity(1)\n")
  959.      else:
  960.         Tofile.write(IND+VarName+".SetCaseSensitivity(0)\n")
  961.    #enddef __init__
  962.  
  963.    def PutLex(self):
  964.      IND = self.I
  965.      Tofile = self.File
  966.      VarName = self.Var
  967.      LexD = self.Gram.LexD
  968.      tokens = self.tokens
  969.  
  970.      Tofile.write("\n\n"+IND+"# declaration of lexical dictionary.\n")
  971.      Tofile.write(IND+"# EXCEPT FOR TERMINALS\n")
  972.      Tofile.write(IND+VarName+".LexD.punctuationlist = ")
  973.      Tofile.write(`LexD.punctuationlist`+"\n")
  974.      Tofile.write(IND+"# now comment patterns\n")
  975.      for comment in LexD.commentstrings:
  976.         Tofile.write(IND+VarName+".LexD.comment("+`comment`+")\n")
  977.      Tofile.write(IND+"# now define tokens\n")
  978.      for i in range(0,len(tokens)):
  979.         tok = tokens[i]
  980.         (kind, name) = tok
  981.         if kind == TERMFLAG:
  982.            # put warning at end!
  983.            #  nonterminal not installed in lexical dictionary here!
  984.            Tofile.write(IND+VarName+".IndexToToken["+`i`+"] = ")
  985.            Tofile.write(PMODULE+".termrep("+`name`+")\n")           
  986.         elif kind == KEYFLAG:
  987.            Tofile.write(IND+VarName+".IndexToToken["+`i`+"] = ")
  988.            Tofile.write(VarName+".LexD.keyword("+`name`+")\n")
  989.         elif kind == NONTERMFLAG:
  990.            Tofile.write(IND+VarName+".IndexToToken["+`i`+"] = ")
  991.            Tofile.write(PMODULE+".nonterminal("+`name`+")\n")
  992.         else:
  993.            raise FlowError, "unknown token type"
  994.    #enddef PutLex
  995.  
  996.    def PutRules(self):
  997.      IND = self.I
  998.      VarName = self.Var
  999.      Rules = self.Gram.RuleL
  1000.      Tofile = self.File
  1001.      Root = self.Gram.DFA.root_nonTerminal
  1002.      Tofile.write("\n\n"+IND+"# declaration of rule list with names.\n")
  1003.      Tofile.write(IND+"# EXCEPT FOR INTERP FUNCTIONS\n")
  1004.      nrules = len(Rules)
  1005.      Tofile.write(IND+VarName+".RuleL = [None] * "+`nrules`+"\n")
  1006.      for i in range(0,nrules):
  1007.         # put warning at end:
  1008.         #  rule reduction function not initialized here!
  1009.         rule = Rules[i]
  1010.         name = rule.Name
  1011.         Tofile.write(IND+"rule = "+`rule`+"\n")
  1012.         Tofile.write(IND+"name = "+`name`+"\n")
  1013.         Tofile.write(IND+"rule.Name = name\n")
  1014.         Tofile.write(IND+VarName+".RuleL["+`i`+"] = rule\n")
  1015.         Tofile.write(IND+VarName+".RuleNameToIndex[name] = "+`i`+"\n")
  1016.  
  1017.      Tofile.write("\n\n"+IND+"# DFA root nonterminal.\n")
  1018.      Tofile.write(IND+VarName+".DFA.root_nonTerminal =")
  1019.      Tofile.write(`Root`+"\n")
  1020.    #enddef PutRules
  1021.  
  1022.    def PutTransitions(self):
  1023.      IND = self.I
  1024.      Tofile = self.File
  1025.      VarName = self.Var
  1026.      maxState = self.Gram.DFA.maxState
  1027.      tokenToInt = self.tokInt
  1028.      StateTokenMap = self.Gram.DFA.StateTokenMap
  1029.      keys = self.keys
  1030.  
  1031.      Tofile.write("\n\n"+IND+"# DFA state declarations.\n")
  1032.      for state in range(1, maxState+1):
  1033.         Tofile.write(IND+VarName+".DFA.States["+`state`+"] = ")
  1034.         Tofile.write('['+`TRANSFLAG`+']\n')
  1035.      Tofile.write(IND+VarName+".DFA.maxState = "+`maxState`+"\n")
  1036.  
  1037.      Tofile.write("\n\n"+IND+"# DFA transition declarations.\n")
  1038.      for key in keys:
  1039.         (fromState, TokenRep) = key
  1040.         TokenIndex = tokenToInt[TokenRep]
  1041.         TokenArg = VarName+".IndexToToken["+`TokenIndex`+"]"
  1042.         TMap = StateTokenMap[key]
  1043.         TMaptype = TMap[0][0]
  1044.         if TMaptype == REDUCEFLAG:
  1045.            # reduction
  1046.            rulenum = TMap[0][1]
  1047.            Args = "("+`fromState`+","+TokenArg+","+`rulenum`+")"
  1048.            Tofile.write(IND+VarName+".DFA.SetReduction"+Args+"\n")
  1049.         elif TMaptype == MOVETOFLAG:
  1050.            # MoveTo
  1051.            Args = "("+`fromState`+","+TokenArg+","+`TMap[0][1]`+")"
  1052.            Tofile.write(IND+VarName+".DFA.SetMap"+Args+"\n")
  1053.         else:
  1054.            raise FlowError, "unexpected else (2)"
  1055.    #enddef
  1056.  
  1057.    def Cleanup(self):
  1058.      Tofile = self.File
  1059.      RuleL = self.Gram.RuleL
  1060.      tokens = self.tokens
  1061.      VarName = self.Var
  1062.      IND = self.I
  1063.      FName = self.FName
  1064.  
  1065.      Tofile.write("\n\n"+IND+"# Clean up the grammar.\n")
  1066.      Tofile.write(IND+VarName+".CleanUp()\n")
  1067.  
  1068.      # if the Fname was given return the grammar as function result
  1069.      if FName != None:
  1070.         Tofile.write("\n\n"+IND+"# return the grammar.\n")
  1071.         Tofile.write(IND+"return "+VarName+"\n")
  1072.  
  1073.      Tofile.write("\n\n"+IND+"# WARNINGS ****************************** \n")
  1074.      Tofile.write(IND+"# You must bind the following rule names \n")
  1075.      Tofile.write(IND+"# to reduction interpretation functions \n")
  1076.      for R in RuleL:
  1077.         Tofile.write(IND+"# "+VarName+".Bind("+`R.Name`+", ??function??)\n")
  1078.      Tofile.write(IND+"#(last rule)\n")
  1079.  
  1080.      Tofile.write("\n\n"+IND+"# WARNINGS ****************************** \n")
  1081.      Tofile.write(IND+"# You must bind the following terminals \n")
  1082.      Tofile.write(IND+"# to regular expressions and interpretation functions \n")
  1083.      warningPrinted = 0
  1084.      for tok in tokens:
  1085.         (kind, name) = tok
  1086.         if kind == TERMFLAG and tok != ENDOFFILETOKEN:
  1087.            Tofile.write(IND+"# "+VarName+\
  1088.              ".Addterm("+`name`+", ??regularExp??, ??function??)\n")
  1089.            warningPrinted = 1
  1090.      if not warningPrinted:
  1091.         Tofile.write(IND+"#  ***NONE** \n")
  1092.      Tofile.write(IND+"#(last terminal)\n")
  1093.      Tofile.write(IND+"# ******************************END RECONSTRUCTION\n")
  1094.    #enddef
  1095. #endclass
  1096.  
  1097. # reconstruction using marshalling to a file
  1098. #  encodes internal structures for grammar using marshal-able
  1099. #  objects.  Final marshalling to the file is done at CleanUp()
  1100. #  storing one big tuple.
  1101. #
  1102. class marshalReconstruct(Reconstruct):
  1103.  
  1104.    def __init__(self, Grammar, Tofile):
  1105.      self.Gram = Grammar
  1106.      self.File = Tofile
  1107.      # should archive self.tokens structure
  1108.      self.MakeTokenArchives()
  1109.      # archive this
  1110.      self.CaseSensitivity = Grammar.LexD.isCaseSensitive()
  1111.  
  1112.    def PutLex(self):
  1113.      LexD = self.Gram.LexD
  1114.      # archive these
  1115.      self.punct = LexD.punctuationlist
  1116.      self.comments = LexD.commentstrings
  1117.  
  1118.    def PutRules(self):
  1119.      # archive this
  1120.      self.Root = self.Gram.DFA.root_nonTerminal
  1121.      # make a list of tuples that can be used with
  1122.      # rule = apply(ParseRule, tuple[1])
  1123.      # rule.Name = tuple[0]
  1124.      Rules = self.Gram.RuleL
  1125.      nrules = len(Rules)
  1126.      RuleTuples = [None] * nrules
  1127.      for i in range(nrules):
  1128.         rule = Rules[i]
  1129.         RuleTuples[i] = (rule.Name, rule.components())
  1130.      #archive this
  1131.      self.RuleTups = RuleTuples
  1132.  
  1133.    def PutTransitions(self):
  1134.      keys = self.keys
  1135.      tokenToInt = self.tokInt
  1136.      StateTokenMap = self.Gram.DFA.StateTokenMap
  1137.      
  1138.      # archive this
  1139.      self.MaxStates = self.Gram.DFA.maxState
  1140.  
  1141.      # create two lists, 
  1142.      #   one for reductions with contents (fromState, tokennumber, rulenum)
  1143.      #   one for movetos with contents (fromstate, tokennumber, tostate)
  1144.      #      (note: token number not token itself to allow sharing)
  1145.      # to allow arbitrary growing, first use dicts:
  1146.      reductDict = {}
  1147.      nreducts = 0
  1148.      moveToDict = {}
  1149.      nmoveTos = 0
  1150.      for key in self.keys:
  1151.         (fromState, TokenRep) = key
  1152.         TokenIndex  = tokenToInt[TokenRep]
  1153.         TMap = StateTokenMap[key]
  1154.         TMaptype = TMap[0][0]
  1155.         if TMaptype == REDUCEFLAG:
  1156.            rulenum = TMap[0][1]
  1157.            reductDict[nreducts] = (fromState, TokenIndex, rulenum)
  1158.            nreducts = nreducts + 1
  1159.         elif TMaptype == MOVETOFLAG:
  1160.            ToState = TMap[0][1]
  1161.            moveToDict[nmoveTos] = (fromState, TokenIndex, ToState)
  1162.            nmoveTos = nmoveTos + 1
  1163.         else:
  1164.            raise FlowError, "unexpected else"
  1165.      #endfor
  1166.      # translate dicts to lists
  1167.      reducts = [None] * nreducts
  1168.      for i in range(nreducts):
  1169.         reducts[i] = reductDict[i]
  1170.      moveTos = [None] * nmoveTos
  1171.      for i in range(nmoveTos):
  1172.         moveTos[i] = moveToDict[i]
  1173.  
  1174.      # archive these
  1175.      self.reducts = reducts
  1176.      self.moveTos = moveTos
  1177.  
  1178.    # this is the function that does the marshalling
  1179.    def Cleanup(self):
  1180.      import marshal
  1181.      # make the big list to marshal
  1182.      BigList = [None] * 9
  1183.      BigList[0] = self.tokens
  1184.      BigList[1] = self.punct
  1185.      BigList[2] = self.comments
  1186.      BigList[3] = self.RuleTups
  1187.      BigList[4] = self.MaxStates
  1188.      BigList[5] = self.reducts
  1189.      BigList[6] = self.moveTos
  1190.      BigList[7] = self.Root
  1191.      BigList[8] = self.CaseSensitivity
  1192.      # dump the big list to the file
  1193.      marshal.dump( BigList, self.File )
  1194.  
  1195. #end class
  1196.  
  1197. #######################testing stuff
  1198. if RUNTESTS:
  1199.   def echo(x): return x
  1200.   
  1201.   # simple grammar stolen from a text
  1202.   LD0 = kjParser.LexDictionary()
  1203.   id = LD0.terminal("id","id",echo)
  1204.   plus = LD0.punctuation("+")
  1205.   star = LD0.punctuation("*")
  1206.   oppar = LD0.punctuation("(")
  1207.   clpar = LD0.punctuation(")")
  1208.   equals = LD0.punctuation("=")
  1209.   E = kjParser.nonterminal("E")
  1210.   T = kjParser.nonterminal("T")
  1211.   Tp = kjParser.nonterminal("Tp")
  1212.   Ep = kjParser.nonterminal("Ep")
  1213.   F = kjParser.nonterminal("F")
  1214.   rule1 = kjParser.ParseRule( E, [ T, Ep ] )
  1215.   rule2 = kjParser.ParseRule( Ep, [ plus, T, Ep ] )
  1216.   rule3 = kjParser.ParseRule( Ep, [ ] )
  1217.   rule4 = kjParser.ParseRule( T, [ F, Tp ] )
  1218.   rule5 = kjParser.ParseRule( Tp, [ star, F, Tp ] )
  1219.   rule6 = kjParser.ParseRule( Tp, [ ] )
  1220.   rule7 = kjParser.ParseRule( F, [ oppar, E, clpar ] )
  1221.   rule8 = kjParser.ParseRule( F, [ id ] )
  1222.   
  1223.   rl0 = [ rule1, rule2, rule3, rule4, rule5, rule6, rule7,rule8]
  1224.   rs0 = ruleset(E, rl0)
  1225.   rs0.CompFirst()
  1226.   Firstpairs = kjSet.GetPairs(rs0.First)
  1227.   rs0.CompFollow()
  1228.   Followpairs = kjSet.GetPairs(rs0.Follow)
  1229.   rs0.CompSLRNFA()
  1230.   NFA0 = rs0.SLRNFA
  1231.   rs0.CompDFA()
  1232.   rs0.SLRFixDFA()
  1233.   DFA0 = rs0.DFA
  1234.   
  1235.   class dummy: pass
  1236.   ttt0 = dummy()
  1237.   
  1238.   def TESTDFA( STRING , ttt, DFA, Rulelist, DOREDUCTIONS = 1):
  1239.     ttt.STRING = STRING
  1240.     #ttt.List = kjParser.LexList(LD0, ttt.STRING)
  1241.     ttt.Stream = kjParser.LexStringWalker( ttt.STRING, LD0 )
  1242.     ttt.Stack = {-1:0}# Walkers.SimpleStack()
  1243.     ttt.ParseObj = kjParser.ParserObj( Rulelist, \
  1244.                        ttt.Stream, DFA, ttt.Stack,DOREDUCTIONS)
  1245.     ttt.RESULT = ttt.ParseObj.GO()
  1246.     #ttt.Stack.Dump(10)
  1247.     return ttt.RESULT
  1248.   
  1249.   def TESTDFA0( STRING , DOREDUCTIONS = 1):
  1250.     return TESTDFA( STRING, ttt0, DFA0, rl0, DOREDUCTIONS )
  1251.   
  1252.   TESTDFA0( " id + id * id ")
  1253.   
  1254.   # an even simpler grammar
  1255.   S = kjParser.nonterminal("S")
  1256.   M = kjParser.nonterminal("M")
  1257.   A = kjParser.nonterminal("A")
  1258.   rr1 = kjParser.ParseRule( S, [M] )
  1259.   #rr2 = kjParser.ParseRule( A, [A, plus, M])
  1260.   #rr3 = kjParser.ParseRule( A, [M], echo)
  1261.   #rr4 = kjParser.ParseRule( M, [M, star, M])
  1262.   rr5 = kjParser.ParseRule( M, [oppar, M, clpar])
  1263.   rr6 = kjParser.ParseRule( M, [id])
  1264.   rl1 = [rr1,rr5,rr6]
  1265.   rs1 = ruleset(S, rl1)
  1266.   rs1.CompFirst()
  1267.   rs1.CompFollow()
  1268.   rs1.CompSLRNFA()
  1269.   rs1.CompDFA()
  1270.   rs1.SLRFixDFA()
  1271.   DFA1 = rs1.DFA
  1272.   
  1273.   ttt1=dummy()
  1274.   
  1275.   def TESTDFA1( STRING , DOREDUCTIONS = 1):
  1276.     return TESTDFA( STRING, ttt1, DFA1, rl1, DOREDUCTIONS )
  1277.   
  1278.   X = kjParser.nonterminal("X")
  1279.   Y = kjParser.nonterminal("Y")
  1280.   RX = kjParser.ParseRule( X, [ oppar, Y, clpar ] )
  1281.   RY = kjParser.ParseRule( Y, [] )
  1282.   rl2 = [RX,RY]
  1283.   rs2 = ruleset(X, rl2)
  1284.   rs2.CompFirst()
  1285.   rs2.CompFollow()
  1286.   rs2.CompSLRNFA()
  1287.   rs2.CompDFA()
  1288.   rs2.SLRFixDFA()
  1289.   DFA2 = rs2.DFA
  1290.   
  1291.   ttt2 = dummy()
  1292.   def TESTDFA2( STRING, DOREDUCTIONS = 1):
  1293.      return TESTDFA( STRING, ttt2, DFA2, rl2, DOREDUCTIONS )
  1294.   
  1295.   # the following grammar should fail to be slr
  1296.   # (Aho,Ullman p. 213)
  1297.   
  1298.   S = kjParser.nonterminal("S")
  1299.   L = kjParser.nonterminal("L")
  1300.   R = kjParser.nonterminal("R")
  1301.   RS1 = kjParser.ParseRule( S, [L, equals, R] )
  1302.   RS2 = kjParser.ParseRule( S, [R], echo )
  1303.   RL1 = kjParser.ParseRule( L, [star, R])
  1304.   RL2 = kjParser.ParseRule( L, [id])
  1305.   RR1 = kjParser.ParseRule( R, [L] )
  1306.   rs3 = ruleset(S, [RS1,RS2,RL1,RL2,RR1])
  1307.   rs3.CompFirst()
  1308.   rs3.CompFollow()
  1309.   rs3.CompSLRNFA()
  1310.   rs3.CompDFA()
  1311.   #rs3.SLRFixDFA() # should fail and does.
  1312.  
  1313.   # testing RULEGRAM
  1314.   ObjG = NullCGrammar()
  1315.   ObjG.Addterm("id","id",echo)
  1316.   ObjG.Nonterms("T E Ep F Tp")
  1317.   ObjG.Keywords("begin end")
  1318.   ObjG.punct("+*()")
  1319.   ObjG.comments(["--.*\n"])
  1320.   # PROBLEM WITH COMMENTS???
  1321.   Rulestr = """
  1322.     ## what a silly grammar!
  1323.     T ::
  1324.     @R One :: T >> begin E end
  1325.     @R Three :: E >>
  1326.     @R Two :: E >> E + T
  1327.     @R Four :: E >> ( T )
  1328.     """
  1329.   RL = RULEGRAM.DoParse1( Rulestr, ObjG )
  1330.